Shareware Grab Bag/Shareware Grab Bag.iso/050/madtrb10.arc/TREE.PAS

Pascal/Delphi Source File | 1985-12-08 | 16.6 KB | 230 lines

Program MailOrder;

{ *************************************************************************** }
{ *                                                                         * }
{ *                   QUEUE AND TREE THEORY PROGRAM                         * }
{ *                             Program #5                                  * }
{ *                                                                         * }
{ *                     Class: CS 367     Section: 4                        * }
{ *                         Instructor: Wiegand                             * }
{ *                                                                         * }
{ *                       Written by Chris Maeder                           * }
{ *                Edited and Compiled using Turbo Pascal                   * }
{ *                            on an IBM PC                                 * }
{ *                                                                         * }
{ *   DEFINITION:                                                           * }
{ *        A queue is a data structure which is used to get                 * }
{ *        first-in/first-out (FIFO) behavior.  Elements can be added to    * }
{ *        the queue but the only element that can be removed from the      * }
{ *        queue is the first-most element in the queue.                    * }
{ *                                                                         * }
{ *        Example queue:                                                   * }
{ *                                                                         * }
{ *         __     __     __     __     __     __     __                    * }
{ *        |__|-->|__|-->|__|-->|__|-->|__|-->|__|-->|__|-->Nil             * }
{ *                                                                         * }
{ *          ^--HeadPtr                                ^--TailPtr           * }
{ *                                                                         * }
{ *        This queue data structure can be represented in computer memory  * }
{ *        as a linked list of elements.  Note that the link between queue  * }
{ *        elements is implemented using pointers.  An ealier element       * }
{ *        points to the next element added to the queue.  A new element    * }
{ *        is inserted at the tail of the queue with the aid of a queue     * }
{ *        element tail pointer.  Note that the only element allowed to be  * }
{ *        removed from the queue is the element at the front of the        * }
{ *        queue.  A queue element head pointer points to the front         * }
{ *        element of the queue.  When the front element is removed from    * }
{ *        the queue its successor becomes the new front queue element.     * }
{ *                                                                         * }
{ *                                                                         * }
{ *        A binary tree is a tree data structure with one root node        * }
{ *        which has two binary trees as child nodes.  A binary search      * }
{ *        tree is a special binary tree whose nodes are organized in an    * }
{ *        ordered manner such that an inorder traversal of the tree        * }
{ *        gives the natural order of the elements.  For each node in a     * }
{ *        binary search tree, elements in its left subtree are before      * }
{ *        it (in natural order) and elements in its right subtree are      * }
{ *        after it (in natural order).                                     * }
{ *                                                                         * }
{ *        A binary search tree is very useful in storing data since it     * }
{ *        allows very fast access search speeds for a particular item.     * }
{ *        The principal reason for this this fast access speed is that     * }
{ *        at every node branch half of the tree data is removed from       * }
{ *        having to be looked at during a search.                          * }
{ *                                                                         * }
{ *        Sample data for the below example:                               * }
{ *                                                                         * }
{ *            Sally Tom George Ed Sam Frank Zena Don                       * }
{ *                                                                         * }
{ *        Example binary search tree whose nodes are ordered               * }
{ *        alphabetically after reading the above data:                     * }
{ *                                                                         * }
{ *                                Sally <--Root                            * }
{ *                               /     \                                   * }
{ *                         George       Tom                                * }
{ *                       / \              / \                              * }
{ *                     Ed   Nil        Sam   Zena                          * }
{ *                   / \             / \       / \                         * }
{ *                Don   Frank     Nil   Nil Nil   Nil                      * }
{ *              / \         / \                                            * }
{ *           Nil   Nil   Nil   Nil                                         * }
{ *                                                                         * }
{ *        The tree data structure can be represented in computer memory    * }
{ *        as tree node elements linked to the rest of the tree by either   * }
{ *        its parent's left child pointer or right child pointer.  Every   * }
{ *        binary search tree node element has a left node pointer          * }
{ *        pointing to a binary search subtree that is before it and a      * }
{ *        right node pointer pointing to a binary search subtree that is   * }
{ *        after it.                                                        * }
{ *                                                                         * }
{ *        It should be noted that new nodes are always inserted into a     * }
{ *        binary search tree as leaf nodes.                                * }
{ *                                                                         * }
{ *        Note that there are three special cases when deleting an         * }
{ *        element from a binary search tree:                               * }
{ *                                                                         * }
{ *              1. Delete an element with no children.                     * }
{ *              2. Delete an element with one child.                       * }
{ *              3. Delete an element with two children.                    * }
{ *                                                                         * }
{ *                                                                         * }
{ *   ALGORITHM:                                                            * }
{ *        Specific algorithms can be found with their respectful           * }
{ *        functions, procedures, and modules.                              * }
{ *                                                                         * }
{ *                                                                         * }
{ *   PURPOSE:                                                              * }
{ *        1. Print report heading.                                         * }
{ *        2. Process mail orders for a sporting goods store.               * }
{ *        3. The following data structures are to be used:                 * }
{ *           a. Use queues to hold transactions waiting to be processed.   * }
{ *           b. Use a circular doubly linked queue to maintain the         * }
{ *              employee list and current working employee.                * }
{ *           c. Use a binary search tree to hold the merchandise the       * }
{ *              store carries.                                             * }
{ *        4. All data structures are to be implemented using pointers.     * }
{ *        5. Employee commands are to be processed as they are read in     * }
{ *           from the date file.                                           * }
{ *           a. Hire an already existant clerk?  Ignore the command.       * }
{ *           b. An non-existant clerk quits?  Ignore the command.          * }
{ *           c. Otherwise process the command.                             * }
{ *        6. Each clerk does just two transactions.                        * }
{ *           a. A clerk that does one transaction at the end of the day    * }
{ *              does their second transaction at the start of the next     * }
{ *              day.                                                       * }
{ *        7. Transactions are to be processed one day at a time in the     * }
{ *           following order:                                              * }
{ *           a. New item transaction                                       * }
{ *              i.   Try to insert an already available item?  Treat it    * }
{ *                   as an add transaction.                                * }
{ *              ii.  Otherwise process the transaction.                    * }
{ *           b. Add a quantity to an item.                                 * }
{ *              i.   Try to add to a non-existant item?  Ignore the        * }
{ *                   transaction.                                          * }
{ *              ii.  Otherwise process the transaction.                    * }
{ *           c. Sell items                                                 * }
{ *              i.   Transactions processed first come, first serve.       * }
{ *              ii.  Try to sell a non-existant item?  Delay the           * }
{ *                   transaction until the next day.                       * }
{ *              iii. The item exists but the quantity is not sufficient?   * }
{ *                   Delay the transaction until the next day.             * }
{ *              iv.  Otherwise process the transaction.                    * }
{ *              v.   Note that a sell transaction may stay on the queue    * }
{ *                   the entire time.                                      * }
{ *           d. Remove items                                               * }
{ *              i.   Try to remove a non-existant item?  Ignore the        * }
{ *                   transaction.                                          * }
{ *              ii.  Otherwise process the transaction.                    * }
{ *                                                                         * }
{ *                                                                         * }
{ *   INPUT/OUTPUT:                                                         * }
{ *        1. Print program heading.                                        * }
{ *        2. Read the mail order transactions out of the data file.        * }
{ *        3. Output should be very clear and well spaced.                  * }
{ *        4. For each day the following output should be printed:          * }
{ *           a. Print each transaction as it is processed off of the       * }
{ *              queue.                                                     * }
{ *              i.   Print the type of transaction.                        * }
{ *              ii.  Print the mail order clerk that processed it.         * }
{ *           b. Print a list of current clerks.                            * }
{ *           c. Print a list of items left on the queues.                  * }
{ *        5. Print the inventory binary search tree out in alphabetical    * }
{ *           order.                                                        * }
{ *        6. Print the binary search tree out in tree form.                * }
{ *                                                                         * }
{ *                                                                         * }
{ *************************************************************************** }

Const
  MAX_ENTRY_SIZE=25;                   { maximum size of entry string }
  MAX_CLERK_NAME_SIZE=25;              { maximum size of clerk names }
  MAX_ITEM_NAME_SIZE=20;               { maximum size of item names }
  MAX_FILE_ENTRY_SIZE=55;              { maximum size of the fiel entry string }
  FILE_NAME='Tree.Fil';
  L_PRINT=False;                       { a boolean used to control the re-direction of the output to the printer }

Type
  EntryString=String[MAX_ENTRY_SIZE];  { a string type used to store queue entries }
  ClerkString=String[MAX_CLERK_NAME_SIZE]; { a string type used to store clerk names }
  ItemString=String[MAX_ITEM_NAME_SIZE]; { a string type used to store item names }
  FileEntryString=String[MAX_FILE_ENTRY_SIZE]; { a string type used to store file entries }

  QueueElementPtr=^QueueElementType;   { a pointer which points to the data record type 'QueueElementType' }
  QueueElementType=                    { a doubly linked data record type used to store information in a queue }
    Record
      ItemName:EntryString;
      ItemQuantity:EntryString;
      Front:QueueElementPtr;           { a pointer to forward queue element }
      Back:QueueElementPtr;            { a pointer to rearward queue element }
    End; { QueueElementType }

  EmployeePtr=^EmployeeType;           { a pointer which points to the data record type 'QueueElementType' }
  EmployeeType=                        { a doubly linked data record type used to store information in a queue }
    Record
      EmployeeName:EntryString;
      ItemsProcessedDuringShift:Integer; { a counter used to keep track of how many items the employee
                                           processed during his shift }
      NextEmployee:EmployeePtr;        { a pointer to the next employee to take his shift }
      LastEmployee:EmployeePtr;        { a pointer to the last employee to have his shift }
    End; { EmployeeType }

  TreeNodePtr=^TreeNodeElementType;    { a pointer which points to the data record type 'TreeNodeElementType' }
  TreeNodeElementType=                 { a binary tree node data type }
    Record
      ItemName:EntryString;
      ItemQuantity:Integer;
      Left:TreeNodePtr;                { a pointer to left tree node on next lower level }
      Right:TreeNodePtr;               { a pointer to right tree node on next lower level }
    End; { TreeNodeElementType }


Var
  NewItemHeadPtr,NewItemTailPtr:QueueElementPtr;           { pointers to the front and rear of the queue used to store
                                                             new items to be added to the store's inventory }
  AddQuantityHeadPtr,AddQuantityTailPtr:QueueElementPtr;   { pointers to the front and rear of the queue used to store
                                                             item stock shipments }
  SellQuantityHeadPtr,SellQuantityTailPtr:QueueElementPtr; { pointers to the front and rear of the queue used to store
                                                             items sold from the store's stock }
  RemoveItemHeadPtr,RemoveItemTailPtr:QueueElementPtr;     { pointers to the front and rear of the queue used to store
                                                             items to be removed from the store's inventory }
  CurrentEmployeePtr:EmployeePtr;                          { a pointer which points to the current employee that is
                                                             on his work shift }
  HoldPtr:Integer;                                         { a temporary pointer used in the re-directing of output
                                                             from the screen to the printer }
  TreeRootPtr:TreeNodePtr;                                 { a pointer which points to the root of the binary search
                                                             tree which stores the store's inventory }

{$I Tree.Inc} { compliler include directive to include the file 'Tree.Inc' }


Begin   { Main Program }
  HoldPtr:=ConOutPtr;                  { temporarily store current output device address }
  If L_PRINT Then
    ConOutPtr:=LstOutPtr;              { re-direct output to the printer }
  PrintHeading;
  InitPointers;
  ReadInputFile;
  PrintInventoryModule;
  PrintBinaryTree;
  ConOutPtr:=HoldPtr;                  { reset output device address }
End.    { Main Program }